{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Best Time to Buy and Sell Stock II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxProfit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #买卖股票的最佳时机 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>prices</code> ，其中&nbsp;<code>prices[i]</code> 表示某支股票第 <code>i</code> 天的价格。</p>\n",
    "\n",
    "<p>在每一天，你可以决定是否购买和/或出售股票。你在任何时候&nbsp;<strong>最多</strong>&nbsp;只能持有 <strong>一股</strong> 股票。你也可以先购买，然后在 <strong>同一天</strong> 出售。</p>\n",
    "\n",
    "<p>返回 <em>你能获得的 <strong>最大</strong> 利润</em>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>prices = [7,1,5,3,6,4]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。\n",
    "&nbsp;    随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。\n",
    "     总利润为 4 + 3 = 7 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>prices = [1,2,3,4,5]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。\n",
    "&nbsp;    总利润为 4 。</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>prices = [7,6,4,3,1]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= prices.length &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= prices[i] &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [best-time-to-buy-and-sell-stock-ii](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [best-time-to-buy-and-sell-stock-ii](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[7,1,5,3,6,4]', '[1,2,3,4,5]', '[7,6,4,3,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        #find all increase interval\n",
    "        if len(prices) == 0 or len(prices) == 1:\n",
    "            return 0\n",
    "        \n",
    "        buy_pt = 0\n",
    "        sell_pt = 0\n",
    "        total = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            if prices[i-1] <= prices[i]:\n",
    "                sell_pt = i\n",
    "                if buy_pt is None:\n",
    "                    buy_pt = i - 1\n",
    "            else:\n",
    "                if buy_pt is not None:\n",
    "                    total += prices[sell_pt] - prices[buy_pt]\n",
    "                    buy_pt = None\n",
    "                    sell_pt = None\n",
    "        if buy_pt is not None:\n",
    "            total += prices[sell_pt] - prices[buy_pt]\n",
    "        return total\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not prices:\n",
    "            return 0\n",
    "        result=0\n",
    "        for i in range(1,len(prices)):\n",
    "            if prices[i]>prices[i-1]:\n",
    "                result+=(prices[i]-prices[i-1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not len(prices):\n",
    "            return 0\n",
    "        prices.append(0)\n",
    "        minPrice = float('inf')\n",
    "        lastPrice = prices[0]\n",
    "        sumProfit = 0\n",
    "        for  price in prices:\n",
    "            if lastPrice>price:\n",
    "                minPrice = price\n",
    "                sumProfit += lastProfit\n",
    "            minPrice = min(minPrice,price)\n",
    "            profit = price - minPrice\n",
    "            lastProfit = profit\n",
    "            lastPrice = price\n",
    "        return sumProfit\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: 'List[int]') -> 'int':\n",
    "        l = len(prices)\n",
    "        if l == 0 or l == 1:\n",
    "            return 0\n",
    "        result = [0] * l\n",
    "        m = [0] * l\n",
    "        m[0] = 7\n",
    "        temp = prices[0]\n",
    "        for i in range(1, l):\n",
    "            if temp >= prices[i]:\n",
    "                result[i] = result[i-1]\n",
    "                temp = min(temp, prices[i])\n",
    "                continue\n",
    "            m[i-1] = prices[i-1]\n",
    "            for h in range(i-1, -1, -1):\n",
    "                m[h] = min(m[i-1],m[h])\n",
    "                if m[h] == temp:\n",
    "                    result[i] = max(result[i], result[i-1], prices[i]-temp + (result[h-1] if h > 0 else 0))\n",
    "                    break\n",
    "                elif m[h] >= prices[i]:\n",
    "                    continue\n",
    "                else:\n",
    "                    if m[h] < prices[i]:\n",
    "                        result[i] = max(result[i], result[i-1], prices[i]-m[h]+ (result[h-1] if h > 0 else 0) )\n",
    "            temp = min(temp, prices[i])\n",
    "        return result[l-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if prices == []:\n",
    "            return 0\n",
    "        cash = 0\n",
    "        hold = -prices[0]\n",
    "        \n",
    "        for i in prices:\n",
    "            cash = max(cash,hold + i)\n",
    "            hold = max(hold,cash-i)\n",
    "        return cash"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        i=0\n",
    "        tmp = 0\n",
    "        while i<len(prices)-1:\n",
    "            if prices[i] >=prices[i+1]:\n",
    "                a=0\n",
    "            else:\n",
    "                a=prices[i+1]-prices[i]\n",
    "            tmp += a\n",
    "            i += 1\n",
    "        return tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        profit = 0\n",
    "        for i in range(0, len(prices)-1):\n",
    "            if prices[i+1] > prices[i]:\n",
    "                profit += prices[i+1] - prices[i]\n",
    "        return profit\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(prices);\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        s0, s1, s2 = 0, -prices[0], -prices[0]\n",
    "        \n",
    "        for i in range(n):\n",
    "            s0, s1, s2 = max(s0, s2), max(max(s0 - prices[i], s1), s2 - prices[i]), s1 + prices[i]\n",
    "        \n",
    "        return max(s0, s2);\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        result = 0\n",
    "        for i in range(0, len(prices)):\n",
    "            if i+1 < len(prices):\n",
    "                if prices[i+1] >= prices[i]:\n",
    "                    print(prices[i+1],prices[i])\n",
    "                    result += (prices[i+1] - prices[i])\n",
    "        return result \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(prices)<2:\n",
    "            return 0\n",
    "        \n",
    "        benefit = 0\n",
    "        buy_sold = []\n",
    "        for i in range(len(prices)-1):\n",
    "            if prices[i] < prices[i+1] and len(buy_sold) == 0:\n",
    "                buy_sold.append(prices[i])\n",
    "            if prices[i] > prices[i+1] and len(buy_sold) == 1:\n",
    "                benefit += prices[i]-buy_sold.pop()\n",
    "            print(buy_sold)\n",
    "        if len(buy_sold) == 1:\n",
    "            benefit += prices[-1]-buy_sold.pop()\n",
    "                \n",
    "        return benefit\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if prices==[]:\n",
    "            return 0\n",
    "        l = len(prices)\n",
    "        buy  = 0\n",
    "        sell = 1\n",
    "        now = 0\n",
    "        last = prices[0]\n",
    "        buyp = 0\n",
    "        earn =0\n",
    "        for i in range(1,l):\n",
    "            print(prices[i])\n",
    "            if prices[i-1]<prices[i] and buy == 0 :\n",
    "                print(\"buy\")\n",
    "                buy =1\n",
    "                buyp = prices[i-1]\n",
    "            if  prices[i-1]>prices[i] and buy ==1:\n",
    "                print(\"sell\")\n",
    "                buy = 0\n",
    "                earn += prices[i-1] - buyp\n",
    "            if buy ==1 and i == l-1:\n",
    "                print(\"sell\")\n",
    "                buy = 0\n",
    "                earn += prices[i] - buyp\n",
    "        return earn\n",
    "                \n",
    "                \n",
    "#             now = prices[i]\n",
    "#             print(now)\n",
    "#             if buy ==0 and sell ==1 and now <last:\n",
    "#                 print(\"buy\")\n",
    "#                 buy =1\n",
    "#                 buyp = now\n",
    "#                 sell = 0\n",
    "                \n",
    "#             if buy ==1 and (sell ==0 or i ==l-1)and buyp <now :\n",
    "#                 print(\"sell\")\n",
    "#                 sell =1\n",
    "#                 earn += now-buyp\n",
    "#                 buy = 0 \n",
    "        # return earn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not prices:return 0\n",
    "        dp = [[0]*2 for _ in range(len(prices))]\n",
    "        dp[0][0], dp[0][1] = 0, -prices[0]\n",
    "        for i in range(1, len(prices)):\n",
    "            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])\n",
    "            dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1])\n",
    "        return dp[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not prices:\n",
    "            return 0\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        profit = [[0 for _ in range(2)] for _ in range(len(prices))]\n",
    "\n",
    "        # 0 未购买 1 已持有\n",
    "        profit[0][0], profit[0][1] = 0, -prices[0]\n",
    "\n",
    "        for i in range(1, len(prices)):\n",
    "            profit[i][0] = max(profit[i - 1][0], profit[i - 1][1] + prices[i])\n",
    "            profit[i][1] = max(profit[i - 1][1], profit[i - 1][0] - prices[i])\n",
    "            res = max(res, profit[i][0], profit[i][1])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        profit0 = 0\n",
    "        profit1 = - max(prices) - 100 if len(prices) > 0 else -100\n",
    "        for price in prices:\n",
    "            p0 = max(profit0, profit1 + price)\n",
    "            p1 = max(profit1, profit0 - price)\n",
    "            profit0 = p0\n",
    "            profit1 = p1\n",
    "        return profit0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: 'List[int]') -> 'int':\n",
    "        if len(prices) == 0:\n",
    "            return 0\n",
    "        profit = 0\n",
    "        current = prices[0]\n",
    "        for i in range(1, len(prices)):\n",
    "            if prices[i] < prices[i - 1]:\n",
    "                profit += (prices[i - 1] - current)\n",
    "                current = prices[i]\n",
    "        profit += (prices[-1] - current)\n",
    "        return profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: 'List[int]') -> 'int':\n",
    "        ben = 0\n",
    "        for i in range(len(prices)-1):\n",
    "            if prices[i]<prices[i+1]:\n",
    "                ben+=prices[i+1]-prices[i]\n",
    "        return ben"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        if prices == []: return 0\n",
    "\n",
    "        m = 0  # 累计利润\n",
    "        for i in range(1, len(prices)):\n",
    "            res = prices[i] - prices[i-1]\n",
    "            if res > 0:\n",
    "                m += res\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        if not len(prices):\n",
    "            return 0\n",
    "        max_profit = 0\n",
    "        for index in range(1,len(prices)):\n",
    "            if prices[index] >= prices[index-1]:\n",
    "                max_profit += (prices[index] - prices[index - 1])\n",
    "        return max_profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        if len(prices) == 0:\n",
    "            return 0\n",
    "        tmp = prices[0]\n",
    "        sum = 0\n",
    "        for index in range(1, len(prices)):\n",
    "            if prices[index] > tmp:\n",
    "                sum += prices[index] - tmp\n",
    "                tmp =  prices[index]\n",
    "            else:\n",
    "                tmp = prices[index]\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        if n < 2:\n",
    "            return 0\n",
    "        dp_i_0, dp_i_1 = 0, -float('inf')\n",
    "        for i in range(n):\n",
    "            temp = dp_i_0\n",
    "            dp_i_0 = max(dp_i_0, dp_i_1 + prices[i])\n",
    "            dp_i_1 = max(dp_i_1, temp - prices[i])\n",
    "        return dp_i_0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            earned = prices[i] - prices[i - 1]\n",
    "            if earned > 0:\n",
    "                res += earned\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, lstPrice: List[int]) -> int:\n",
    "        iSum = 0\n",
    "        iBuy = -1\n",
    "        for iDay in range(len(lstPrice) - 1):\n",
    "            if lstPrice[iDay] < lstPrice[iDay + 1]:\n",
    "                if iBuy < 0:\n",
    "                    iBuy = lstPrice[iDay]\n",
    "                    continue\n",
    "            else:\n",
    "                if iBuy >= 0:\n",
    "                    iSum += lstPrice[iDay] - iBuy\n",
    "                    iBuy = -1\n",
    "        # print(iSum)\n",
    "            # if lstPrice[iDay] > lstPrice[iDay + 1]:\n",
    "            # \tiBuy = iYesterday\n",
    "        if iBuy >= 0:\n",
    "            iSum += lstPrice[-1] - iBuy\n",
    "        return iSum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            if prices[i] > prices[i-1]:\n",
    "                res += prices[i] - prices[i-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        profit = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            tmp = prices[i] - prices[i - 1]\n",
    "            if tmp > 0: profit += tmp\n",
    "        return profit\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        iSum = 0\n",
    "        for iDay in range(len(prices) - 1):\n",
    "            if prices[iDay + 1] > prices[iDay]:\n",
    "                iSum += prices[iDay + 1] - prices[iDay]\n",
    "        return iSum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        result = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            if prices[i] - prices[i-1] > 0:\n",
    "                result += (prices[i] - prices[i-1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        max_profit = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            profit = prices[i] - prices[i-1]\n",
    "            if profit > 0:\n",
    "                max_profit += profit\n",
    "        return max_profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        buy, sell = -inf, 0\n",
    "        for p in prices:\n",
    "            buy = max(buy, sell - p)\n",
    "            sell = max(sell, buy + p)\n",
    "        return sell"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        ans = 0\n",
    "        d = []\n",
    "        for i in range(1, len(prices)):\n",
    "            d = prices[i] - prices[i - 1]\n",
    "            if d > 0:\n",
    "                ans += d\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        ans = 0\n",
    "        d = []\n",
    "        for i in range(1, len(prices)):\n",
    "            d.append(prices[i] - prices[i - 1])\n",
    "        for x in d:\n",
    "            if x > 0:\n",
    "                ans += x\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "\n",
    "        n=len(prices)\n",
    "        if n==0 or n==1:\n",
    "            return 0\n",
    "        dp1=[0]*n  # sell out on last day\n",
    "        dp2=[0]*n  # buy in on last day\n",
    "        dp2[0]=-prices[0]\n",
    "\n",
    "        for i in range(1,n):\n",
    "\n",
    "            dp1[i]=max(dp1[i-1],dp2[i-1]+prices[i])\n",
    "            dp2[i]=max(dp2[i-1],dp1[i-1]-prices[i])\n",
    "\n",
    "        #print(dp1)\n",
    "        #print(dp2)\n",
    "        return dp1[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        total, index, length = 0, 0, len(prices)\n",
    "        while (index < length):\n",
    "            while (index < length - 1 and prices[index] >= prices[index + 1]):\n",
    "                index += 1\n",
    "            min = prices[index]\n",
    "            while (index < length - 1 and prices[index] <= prices[index + 1]):\n",
    "                index += 1\n",
    "            total += prices[index] - min\n",
    "            index += 1\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(prices)\n",
    "        for i in range(1, n):\n",
    "            res += max(0, prices[i] - prices[i - 1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        l = len(prices)\n",
    "        if l < 2: return 0\n",
    "\n",
    "        res = 0\n",
    "        for i in range(1,l):\n",
    "            profit = prices[i] - prices[i-1]\n",
    "            if profit > 0:\n",
    "                res += profit\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "\n",
    "        stack = [prices[0]]\n",
    "        res = 0\n",
    "        for i in range(1,len(prices)):\n",
    "            if prices[i]>=stack[-1]:\n",
    "                stack.append(prices[i])\n",
    "            else:\n",
    "                if len(stack)>=2:\n",
    "                    res +=stack[-1] -stack[0] \n",
    "                    stack = [prices[i]]\n",
    "                else:\n",
    "                    stack = [prices[i]]\n",
    "        \n",
    "        if len(stack)>=2:\n",
    "            res += stack[-1] -stack[0]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        # 动态规划：第[]天进行操作/不进行操作的最大利润：那也不行，如果状态转移的话怎么知道当前是否持有？\n",
    "        # 第[]天收市的时候持有/不持有时获得的最大利润\n",
    "        dp_array = [[0] * 2] * len(prices)\n",
    "        dp_array[0][0] = -prices[0]\n",
    "        dp_array[0][1] = 0\n",
    "\n",
    "        for i, price in enumerate(prices[1:]):\n",
    "            dp_array[i][0] = max(dp_array[i-1][0], dp_array[i-1][1] - price) # price 总是正数。\n",
    "            dp_array[i][1] = max(price + dp_array[i-1][0] , dp_array[i-1][1]) # 这里是加，因为我们把买设置为负数，如果减去负数就是加上正数了。\n",
    "\n",
    "        return dp_array[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "\n",
    "        n = len(prices)\n",
    "        dp = [[0] * n for i in range(2)]\n",
    "        dp[0][0] = -prices[0]                             # profit\n",
    "\n",
    "        for i in range(1, n):\n",
    "            dp[0][i] = max(dp[0][i - 1], dp[1][i - 1] - prices[i])                           # hold = buy or hold old\n",
    "            dp[1][i] = max(dp[1][i - 1], prices[i] + dp[0][i - 1])                           # do not hold = sell today or do not hold old\n",
    "\n",
    "        # print(dp)\n",
    "        return dp[1][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        buy = [0] * n\n",
    "        sell = [0] * n\n",
    "        buy[0] = -prices[0]\n",
    "        sell[0] = 0\n",
    "        for i in range(1,n):\n",
    "            buy[i] = max(sell[i-1] - prices[i], buy[i-1])\n",
    "            sell[i] = max(buy[i-1] + prices[i], sell[i-1])\n",
    "        print(buy,sell)\n",
    "        return sell[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "\n",
    "        n = len(prices)\n",
    "        df = [[0] * n for i in range(2)]\n",
    "        df[1][0] = -prices[0]\n",
    "\n",
    "        for i in range(1,n):\n",
    "            df[1][i] = max(df[1][i-1], df[0][i-1] - prices[i])\n",
    "            df[0][i] = max(df[0][i-1], prices[i] + df[1][i-1])\n",
    "        print(df)\n",
    "        return df[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dp = [0]*len(prices)\n",
    "        for i in range(1, len(prices)+1):\n",
    "            if i == 1:\n",
    "                continue\n",
    "            else:\n",
    "                if prices[-i] >= prices[-i+1]:\n",
    "                    dp[-i] = max(dp[-i], max(dp[-i:]))\n",
    "                else:\n",
    "                    dp_tmp = dp[-i:]\n",
    "                    price_tmp = prices[-i:]\n",
    "                    res = [dp_tmp[k]+price_tmp[k]-prices[-i] for k in range(len(dp_tmp))]\n",
    "                    dp[-i] = max(max(res), dp[-i], max(dp_tmp))\n",
    "        # print(dp)\n",
    "\n",
    "        # cnt = 0\n",
    "        # ans = 0\n",
    "        # for i in dp:\n",
    "        #     if i > 0:\n",
    "        #         ans += i\n",
    "        #         cnt += 1\n",
    "        \n",
    "        # if not cnt:\n",
    "        #     return 0\n",
    "        # else:\n",
    "        #     return ans - cnt + 1\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        # dp = [0]*len(prices)\n",
    "        # for i in range(1,len(prices)):\n",
    "        #     for j in range(i):\n",
    "        #         dp[i] = max([dp[i], dp[j], dp[j-1]+prices[i]-prices[j]])\n",
    "        # return max(dp) \n",
    "\n",
    "        dp = [(0,-prices[0])]\n",
    "        for i in range(1, len(prices)):\n",
    "            dp.append((max(dp[-1][0], dp[-1][1]+prices[i]), max(dp[-1][1], dp[-1][0]-prices[i])))\n",
    "        return max(dp[-1])\n",
    "\n",
    "        # ans = 0\n",
    "        # for i in range(1,len(prices)):\n",
    "        #     ans += max(0, prices[i]-prices[i-1])\n",
    "        # return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices) -> int:\n",
    "        dp = [[0, 0] for i in range(len(prices))]\n",
    "        dp[0] = [-prices[0], 0]\n",
    "        for i in range(1, len(prices)):\n",
    "            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])\n",
    "            dp[i][1] = max(dp[i - 1][0] + prices[i], dp[i - 1][1])\n",
    "        return dp[-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maxProfit(self, prices: List[int]) -> int:\n",
    "#         profit = 0\n",
    "#         for i in range(1, len(prices)):\n",
    "#             tmp = prices[i] - prices[i - 1]\n",
    "#             if tmp > 0: \n",
    "#                 profit += tmp\n",
    "#         return profit\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        dp = [[0,0] for _ in range(n)]\n",
    "        dp[0] = [-prices[0], 0]\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = max(dp[i-1][0], - prices[i] + dp[i-1][1])\n",
    "            dp[i][1] = max(dp[i-1][1], + prices[i] + dp[i-1][0])\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        #dp[i][0],dp[i][1]持有与不持有的状态\n",
    "        #dp[i][0] = max(dp[i-1][0],dp[i-1][1]-prices[i])\n",
    "        #dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i])\n",
    "        \n",
    "        length = len(prices)\n",
    "        dp = [[0] * 2 for _ in range(length)]\n",
    "        dp[0][0] = -prices[0]\n",
    "        dp[0][1] = 0\n",
    "        for i in range(1, length):\n",
    "            dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]) \n",
    "            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])\n",
    "        return dp[-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        N = len(prices)\n",
    "        # 定义状态：dp[i][j]表示在第i天持有或卖出时的最大利润，j=1代表持有，j=0代表卖出\n",
    "        dp = [[0 for j in range(2)] for i in range(N)]\n",
    "\n",
    "        # badcase\n",
    "        for i in range(N):\n",
    "            # badcase\n",
    "            if i - 1 == -1:\n",
    "                dp[i][0] = 0\n",
    "                dp[i][1] = -prices[i]\n",
    "            else:\n",
    "                dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])\n",
    "                dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])\n",
    "        return dp[N-1][0]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
